This invention relates to a rule processing system or method that provides automated decision support, but more specifically, to an improvement utilized during decision automation to provide more succinct conflict and selection advice.
During automated rule-based processing, a user may input one or more selections of rule parameters to achieve satisfiability of a rule. Generically, user selections may take the form of enumeration values of rule attributes the relationships among which define the rule. In a product configuration rule for a desktop computer system, for example, an attribute may comprise a computer bundle type and selectable enumerations of that attribute may comprise multimedia, power PC, business workstation, or entry level. Depending on an initial selection of bundle type, enumerations of other product attributes (e.g., CPU speed, DVD speed, Hard Drive Capacity, RAM memory size, etc.) may or may not be compatible.
In order to lessen the amount of effort required of the user to determine and select other compatible enumerations for other attributes, it is desirable to automatically indicate to the user of further compatible selections of enumerations based on the user's initial selections, i.e., to automatically identify or suggest further inputs that satisfy the product configuration rule according to the user's manually-supplied inputs. This requires identification of enumerations that are valid with each other and also valid with the user's initial selections. Such advice more quickly guides the user in choosing correct enumerations for all attributes of the overall rule being processed. Automatic identification/selection of further compatible enumerations is also desirable for other types of business or engineering rule processing system or method.
Thus, this invention is an improvement to the invention disclosed in commonly-owned, incorporated U.S. application Ser. No. 10/101,151 filed Mar. 20, 2002 relating to various rule processing methods, e.g. zero-suppressed binary decision diagrams (ZDDs). The '151 disclosure describes how to generate and combine sets of rules and then to assess satisfiability of those rules as applied to a business or engineering problem.
The related disclosures of U.S. application Ser. No. 10/101,151 filed (now U.S. Pat. No. 6,965,887) and Ser. No. 10/101,154 also show that a ZDD rule representation may be divided into at least two distinct components, i.e., an Include ZDD component and an Exclude ZDD component. This invention deals with improvements to the Exclude ZDD component.
The Include ZDDs contain sets of combinations (e.g., rule components) that are valid together while the Exclude ZDDs contain sets of combinations that can never be valid together. The results from both ZDDs are processed simultaneously to determine the validity of the overall rule represented by the individual Include and Exclude ZDDs. The improvements herein, however, do not necessarily change the underlying validity determination system or method of the aforementioned related disclosures.
The related disclosures also show how to create selection and/or conflict advice based on a set of initial enumerations selected by a user. Such advice is extracted from the Include and the Exclude ZDD representations, as well as an attribute relations ZDD of the rule, to help guide the user in selecting valid combinations of attributes and compatible enumerations for such attributes of the overall rule.
To obtain advice from the Include ZDD rule component, each attribute is considered individually. The processor inspects each attribute in relation to other attributes to determine how potential user selections of enumerations affect the advice for that attribute.
Exclude advice, on the other hand, is generated for all of the attributes at the same time because they indicate enumeration selections that can never be valid together. All of the Exclude enumeration selections are used to find the excluded combinations. Then, the processor calls a ReduceX function to pare down those combinations to the ones that can be excluded on a next user selection.
Lastly, advice from the Include ZDD is compared with the advice from Exclude ZDD. The Include advice identifies which enumerations can be included. The Exclude advice removes some of those Included enumerations.
The present invention also provides an enhancement to commonly-owned incorporated U.S. patent application Ser. No. 10/950,815, filed Sep. 28, 2004, now U.S. Pat. No. 7,552,102, entitled “Rule processing method, apparatus, and computer-readable medium to provide improved selection advice.” The '815 disclosure, among other things, shows how to remove cover details from an Exclude ZDD but the techniques disclosed therein did not effect removal of cover details in all cases. The extent to which the '815 method or the apparatus implementing the same fails to remove cover details, however, was dependent on the particulars of the specific Exclude ZDDs being inspected. Additionally, techniques shown in the '815 disclosure did not necessarily remove all cover details in more than the most trivial of circumstances. The present invention, on the other hand, provides a method (and apparatus implementing the same) that removes cover details across a full range of circumstances.